//给你两个整数：num1 和 num2 。 
//
// 在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2ⁱ + num2 。 
//
// 请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。 
//
// 如果无法使 num1 等于 0 ，返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：num1 = 3, num2 = -2
//输出：3
//解释：可以执行下述步骤使 3 等于 0 ：
//- 选择 i = 2 ，并从 3 减去 2² + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
//- 选择 i = 2 ，并从 1 减去 2² + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
//- 选择 i = 0 ，并从 -1 减去 2⁰ + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
//可以证明 3 是需要执行的最少操作数。
// 
//
// 示例 2： 
//
// 
//输入：num1 = 5, num2 = 7
//输出：-1
//解释：可以证明，执行操作无法使 5 等于 0 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= num1 <= 10⁹ 
// -10⁹ <= num2 <= 10⁹ 
// 
//
// Related Topics 位运算 脑筋急转弯 枚举 👍 48 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-09-05 17:18:44
 * @description 2749.得到整数零需要执行的最少操作数
 
 */
 
public class MinimumOperationsToMakeTheIntegerZero {
    public static void main(String[] args) {
    //测试代码
    MinimumOperationsToMakeTheIntegerZero fun = new MinimumOperationsToMakeTheIntegerZero();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
k*num2+ (2^0 + 2^1 + ... + 2^(k-1)) = num1
可以反向求，每次取最大的2^i
num1 - [ (2^{i1} + num2) + (2^{i2} + num2) + ... + (2^{ik} + num2) ] = 0
num1 = (2^{i1} + 2^{i2} + ... + 2^{ik}) + k * num2
num1 - k * num2 = 2^{i1} + 2^{i2} + ... + 2^{ik}
S = num1 - k * num2
其中S是k个2的幂次方之和


Long.bitCount(x) 给出了用不同 2 的幂次表示 x 所需的最小操作数
如果实际操作次数 ans 大于等于这个最小数，
就可以通过拆分较大的 2 的幂次来达到要求的操作次数

不断的减去nums2，直到余数可以被ans个2的幂次方表示
        * */
    public int makeTheIntegerZero(int num1, int num2) {
        int ans=1;
        while (true){
            long x=num1-(long)ans*num2;
            if(x<ans){
                return -1;
            }
            if(Long.bitCount(x)<=ans){
                return ans;
            }
            ans++;
        }
    }
    // 手动计算二进制中1的个数
    public int makeTheIntegerZero1(int num1, int num2) {
        if (num1 == 0) return 0;

        for (int k = 1; k <= 100; k++) {
            long S = num1 - (long) k * num2;

            // 基本检查
            if (S < 0) {
                if (num2 > 0) return -1;
                continue;
            }
            if (S < k) continue;
            if (S > k * (1L << 60)) continue;

            // 手动计算二进制中1的个数
            int bitCount = 0;
            long temp = S;
            while (temp != 0) {
                bitCount += (temp & 1); // 检查最低位是否为1
                temp >>>= 1; // 无符号右移
            }

            if (bitCount <= k) {
                return k;
            }
        }

        return -1;
    }
    // Brian Kernighan 算法计算1的个数
    public int makeTheIntegerZero2(int num1, int num2) {
        if (num1 == 0) return 0;

        for (int k = 1; k <= 100; k++) {
            long S = num1 - (long) k * num2;

            // 基本检查
            if (S < 0) {
                if (num2 > 0) return -1;
                continue;
            }
            if (S < k) continue;
            if (S > k * (1L << 60)) continue;

            // Brian Kernighan 算法计算1的个数
            int bitCount = 0;
            long n = S;
            while (n != 0) {
                n &= (n - 1); // 清除最低位的1
                bitCount++;
            }

            if (bitCount <= k) {
                return k;
            }
        }

        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
